package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/path-sum-iii/"> 路径总和 III(Path Sum III)</a>
 * <p>给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
 * 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。</p>
 * <p><b>具体题目示例去原题中查看，有图片没法复制</b></p><br>
 * <b>提示:</b>
 * <ul>
 *     <li>二叉树的节点个数的范围是 [0,1000]</li>
 *     <li>-10^9 <= Node.val <= 10^9 </li>
 *     <li>-1000 <= targetSum <= 1000 </li>
 * </ul>
 *
 * @author c2b
 * @see LC0112PathSum_I_S 路径总和 I(Path Sum I)
 * @see LC0113PathSum_II_M 路径总和 II(Path Sum II)
 * @see _LC0437PathSum_M_MMMMM 路径总和 III(Path Sum III)
 * @since 2023/5/22 15:13
 */
public class _LC0437PathSum_M_MMMMM {

    static class Solution {

        public int pathSum1(TreeNode root, int targetSum) {
            Map<Long, Integer> prefixMap = new HashMap<>();
            prefixMap.put(0L, 1);
            return dfs(root, prefixMap, targetSum, 0);
        }

        private int dfs(TreeNode root, Map<Long, Integer> prefixMap, int targetSum, long currSum) {
            if (root == null) {
                return 0;
            }
            int res = 0;
            currSum += root.val;
            res += prefixMap.getOrDefault(currSum - targetSum, 0) + 1;

            prefixMap.put(currSum, prefixMap.getOrDefault(currSum, 0) + 1);


            int left = dfs(root.left, prefixMap, targetSum, currSum);
            int right = dfs(root.right, prefixMap, targetSum, currSum);

            res += left + right;
            prefixMap.put(currSum, prefixMap.get(currSum) - 1);
            return res;
        }

        public int pathSum2(TreeNode root, int targetSum) {
            return pathSumByRecursion(root, targetSum);
        }

        public int pathSumByRecursion(TreeNode root, int targetSum) {
            if (root == null) {
                return 0;
            }
            // 1.找出从根节点出发，所有节点值之和为 targetSum 的路径数目
            // 2.以左子节点为根节点，所有节点值之和为 targetSum 的路径数目
            // 3.以右子节点为根节点，所有节点值之和为 targetSum 的路径数目
            return rootSum(root, targetSum) + pathSumByRecursion(root.left, targetSum) + pathSumByRecursion(root.right, targetSum);

        }

        private int rootSum(TreeNode currNode, long targetSum) {
            int res = 0;
            if (currNode == null) {
                return res;
            }
            targetSum -= currNode.val;
            if (0 == targetSum) {
                ++res;
            }
            return res + rootSum(currNode.left, targetSum) + rootSum(currNode.right, targetSum);
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(10);
        root1.left = new TreeNode(5);
        root1.right = new TreeNode(-3);
        root1.left.left = new TreeNode(3);
        root1.left.right = new TreeNode(2);
        root1.right.right = new TreeNode(11);
        root1.left.left.left = new TreeNode(3);
        root1.left.left.right = new TreeNode(-2);
        root1.left.right.right = new TreeNode(1);

        TreeNode root2 = new TreeNode(1000000000);
        root2.left = new TreeNode(1000000000);
        root2.left.left = new TreeNode(294967296);
        root2.left.left.left = new TreeNode(1000000000);
        root2.left.left.left.left = new TreeNode(1000000000);
        root2.left.left.left.left.left = new TreeNode(1000000000);

        Solution solution = new Solution();
        System.out.println(solution.pathSumByRecursion(root1, 8));
        System.out.println(solution.pathSumByRecursion(root2, 0));
    }
}
